#ifndef _BST_HEADER
#define _BST_HEADER

#include <iostream>

typedef struct BSTNode{
	int value;
	BSTNode *left;
	BSTNode *right;
} *BST;

void insert(BSTNode **node, int const value){
	if(NULL == *node){
		*node = new BSTNode();
		(*node)->value = value;
		(*node)->left = NULL;
		(*node)->right = NULL;
	}
	else if(value < (*node)->value){
		insert(&(*node)->left, value);
	}
	else
		insert(&(*node)->right, value);
}

BST createBST(const int arr[], size_t size){
	// size_t size = sizeof(arr)/sizeof(sizeof(int));
	if(0 == size)
		return NULL;
	BSTNode *bst = NULL;
	// BSTNode *node = bst;
	for(int i = 0; i  < size; i ++){
		insert(&bst, arr[i]); // node = insert(node, arr[i]); the bst will be NULL, why this is different with VS 2010?
	}

	return bst;
}

BSTNode *findNode(BST bst, const int value){
	if(NULL == bst)
		return NULL;

	if(value == bst->value)
		return bst;
	else if(value < bst->value)
		findNode(bst->left, value);
	else
		findNode(bst->right, value);
}

BSTNode* findMinNode(BST bst){
	if(NULL == bst)
		return NULL;
	BSTNode *min = bst;
	while(min->left)
		min = min->left;
	return min;
}

BSTNode* findMaxNode(BST bst){
	if(NULL == bst)
		return NULL;
	BSTNode *max = bst;
	while(max->right)
		max = max->right;
	return max;
}

void deleteNode(BST bst, const int value){
	if(NULL == bst)
		return;
	/*BSTNode *node = findNode(bst, value);*/
	BST p;
	if(value < bst->value)
		deleteNode(bst->left, value);
	else if(value > bst->value)
		deleteNode(bst->right, value);
	else if(NULL != bst->left && NULL != bst->right){
		p = findMinNode(bst->right);
	}
}

void printPre(BSTNode *node){
	if(NULL == node)
		return;
	std::cout << node->value << ", ";
	printPre(node->left);	
	printPre(node->right);
}

void printMid(BSTNode *node){
	if(NULL == node)
		return;
	printMid(node->left);
	std::cout << node->value << ", ";
	printMid(node->right);
}

void printLast(BSTNode *node){
	if(NULL == node)
		return;
	printLast(node->left);
	printLast(node->right);
	std::cout << node->value << ", ";
}


void testBST(){
	int arr[] = {2, 3, 5, 7, 89, 1, 0, 4, 8, 9, 11};
	size_t size = sizeof(arr)/sizeof(sizeof(int));
	BST bst = createBST(arr, size);
	
	BSTNode *p = findNode(bst, 9);

	printMid(bst);
	std::cout << std::endl;
	printPre(bst);
	std::cout << std::endl;
	printLast(bst);
	std::cout << std::endl;
}

int m2main(){
	testBST();
	return 0;
}

#endif // _BST_HEADER